package lc.q1_50;

import java.util.*;

/**
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 */
public class Q32 {

    public int longestValidParentheses(String s) {
        Map<Integer, Integer> positions = new HashMap<>();
        int max = 0;
        for (int i = 0; i < s.length(); ) {
            // 循环次数过多，是不是部分可以不用再看？
            int left = 1;
            if (s.charAt(i)=='(') {
                // 从这里往后找，如果能够减到0，说明i是可以
                int j = i+1;
                for ( ;j < s.length() && left != 0; j++) {
                    if (s.charAt(j) == '(') {
                        left ++;
                    } else {
                        left --;
                    }
                }
                if (left == 0) {
                    // i -> j 是一对完美的
                    Integer integer = positions.get(i);
                    integer = integer==null?i:integer;
                    positions.put(j, integer);
                    max = Math.max(j - integer, max);
                    i = j;
                } else {
                    // 这种情况是不是可以优化？
                    i ++;
                }
            } else {
                i ++;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        // 这种只有2个的
    }
}
